package com.practice.sequence;

import static org.testng.Assert.assertEquals;

import org.testng.annotations.Test;

public class Jump {
	public int minSteps(int[] a) {
		int reach = 0;
		int last = 0;
		int steps = 0;
		
		while (reach < a.length-1) {
			int max = reach;
			for (int i=last; i<=reach && i<a.length; i++) {
				max = Math.max(max, i + a[i]);
			}
			steps++;
			last = reach + 1;
			reach = max;
		}
		
		return steps;
	}
	
	@Test
	public void test() {
		runTest(new int[]{2,3,1,1,4}, 2);
	}
	
	private void runTest(int[] a, int expected) {
		assertEquals(minSteps(a), expected);
	}
}
